/*
 * @lc app=leetcode.cn id=236 lang=cpp
 *
 * [236] 二叉树的最近公共祖先
 */

// @lc code=start

#include <bits/stdc++.h>
using namespace std;

// struct TreeNode
// {
//     int val;
//     TreeNode *left;
//     TreeNode *right;
//     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
// };

class Solution
{

    bool dfs(TreeNode *root, int p, vector<TreeNode *> &pv)
    {
        if (!root)
            return false;
        if (p == root->val)
        {
            pv.push_back(root);
            return true;
        }
        else
        {
            if (dfs(root->left, p, pv))
            {
                pv.push_back(root);
                return true;
            }
            if (dfs(root->right, p, pv))
            {
                pv.push_back(root);
                return true;
            }
        }
        return false;
    }

public:
    TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q)
    {
        vector<TreeNode *> pv, qv;

        if (dfs(root, p->val, pv))
            pv.push_back(root);
        if (dfs(root, q->val, qv))
            qv.push_back(root);
        
        int ip = pv.size() - 1;
        int iq = qv.size() - 1;
        while(ip >= 0 && iq >= 0)
        {
            if(pv[ip] == qv[iq])
            {
                ip--;
                iq--;
            }
            else
            {
                break;
            }
        }

        return pv[ip+1];
    }
};

// @lc code=end
